10810. Это убийство!

Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано одно число. Он нашел это подозрительным и решил запоминать все пройденные числа. Помня пройденные числа, он обнаружил в них закономерность. Детектив решил для каждого числа на лестнице записать сумму всех чисел, которые он ранее наблюдал на лестнице, и которые меньше записанного на текущей ступеньке. Найти сумму всех чисел, записанных в дневнике детектива.

Вход. Первая строка содержит количество тестов t (t ≤ 10). Далее следуют 2t строк. Первая строка задает количество ступенек n (1 ≤ n ≤ 10⁵). Следующая строка содержит n чисел, записанных на ступеньках. Все записанные числа изменяются от 0 до 10⁶.

Выход. Для каждого теста вывести в отдельной строке итоговую сумму.

Пример входа

1

5

1 5 3 6 4

Пример выхода

15

РЕШЕНИЕ

структуры данных – дерево Фенвика

Анализ алгоритма

Числа, записанные на ступеньках, являются целыми и ограничены 0 снизу и 10⁶ сверху. Построим дерево Фенвика по массиву a длины 10⁶ + 1 (индексы массива изменяются от 0 до 10⁶ включительно), изначально элементы которого равны нулю. Каждый раз, когда детектив будет проходить ступеньку со значением value, будем увеличивать a_value на value. При этом в дневнике он будет записывать сумму a₀ + a₁ + a₂ + … + a_value-1.

Учитывая ограничения на входные данные, вычисления следует производить в 64-битовом целочисленном типе.

Пример

Промоделируем записи детектива на приведенном примере. Индексация массива начинается с 0. Числа, записываемые детективом, приведены под стрелками.

Сумма чисел, записанных в дневнике детектива, равна 0 + 1 + 1 + 9 + 4 = 15.

Реализация алгоритма

#include <cstdio>

#include <vector>

#define MAX 1000001

using namespace std;

vector<long long> Fenwick;

int i, n, tests, value;

long long sum;

// a[0] + a[1] + ... + a[i]

long long Summma0_i(int i)

{

long long result = 0;

for (; i >= 0; i = (i & (i + 1)) - 1)

result += Fenwick[i];

return result;

}

// a[i] = a[i] + 1

void IncElement(int i, int delta)

{

for (; i < MAX; i = (i | (i+1)))

Fenwick[i] += delta;

}

int main (void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

Fenwick.assign(MAX,0);

for(sum = i = 0; i < n; i++)

{

scanf("%d",&value);

IncElement(value, value);

sum += Summma0_i(value-1);

}

printf("%lld\n",sum);

}

return 0;

}